package org.algorithm.二师兄.队列.第2周;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @date 2022-04-04 星期一 00:00
 * 给你一个下标从 0 开始的整数数组 nums和一个整数 k。
 *
 * 一开始你在下标0处。每一步，你最多可以往前跳k步，但你不能跳出数组的边界。也就是说，你可以从下标i跳到[i + 1， min(n - 1, i + k)]包含 两个端点的任意位置。
 *
 * 你的目标是到达数组最后一个位置（下标为 n - 1），你的 得分为经过的所有数字之和。
 *
 * 请你返回你能得到的 最大得分。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/jump-game-vi
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class 跳跃游戏 {

    public static void main(String[] args) {
        int[] nums = {1,-1,-2,4,-7,3};
        System.out.println(maxResult(nums, 2));
    }

    public static int maxResult(int[] nums, int k) {
//        /// 条件：      下一步   step = i -> min(i+1, min(n-1, i + k))
//
//        // 动态规划 dp 深入处理
//        int[] dp = new int[nums.length];
//
//        // 定义初始量
//        dp[0] = nums[0];
//
//        // 冒泡， 取最大值， 最大值就是每步的得分。
//        for (int i = 1; i < nums.length; i++) {
//            for (int j = Math.max(0, i - k); j < i; j++) {
//                dp[i] = Math.max(dp[i], dp[j]);
//            }
//            dp[i] += nums[i];
//        }
//        return dp[nums.length - 1];


        // 题解答案看不懂。  TODO   下次再研究。。。。。。
        int len = nums.length;
        Queue<int[]> queue = new PriorityQueue<>((o1, o2) -> o2[0] - o1[0]);
        queue.offer(new int[]{nums[0], 0});
        int res = nums[0];
        for (int i = 1; i < len; i++) {
            while (true){
                assert queue.peek() != null;
                if (!(i - queue.peek()[1] > k)) break;
                queue.poll();
            }
            res = queue.peek()[0] + nums[i];
            queue.offer(new int[]{res, i});
        }
        return res;

    }
}
